package week_02;

import java.util.*;

public class Permutations_2_47 {
    public static List<List<Integer>> ans;
    public static List<Integer> subset;
    public static int[] nums;
    public static boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // dfs 深搜 遍历所有可能性
        ans = new ArrayList<>();
        subset = new ArrayList<>();
        Arrays.sort(nums);
        this.nums = nums;
        //状态表确定数字i是否被用到
        this.used = new boolean[nums.length];
        // 用排序加剪枝
        dfs(0);
        return ans;
    }


    public void dfs(int index) {
        if (index == nums.length) {
            ans.add(new ArrayList<>(subset));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // 跟上一个值相等 且上一个是回退的状态，并没有被使用中
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            } else {
                used[i] = true;
                subset.add(nums[i]);
                dfs(index + 1);
                used[i] = false;
                subset.remove(subset.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,1,3};
        Permutations_2_47 solution =new Permutations_2_47();
        solution.permuteUnique(nums);
    }


}
